/**
 * @Author: lena
 * @Date: 2021/9/23 16:32
 * @Description: 用数组实现环形队列
 * @Version: 1.0.0
 */

package data_structure

import (
    "errors"
)

type queue struct {
    start int
    end int
    size int    // 数组大小
    arr []int   // 用数组模拟队列
}

// 创建一个队列
func NewQueue(size int) *queue {
    return &queue{
        start: 0,
        end: 0,
        size: size+1,   // 由于判断队满队空，需要牺牲掉一个空间，所以为了能够存储size个元素，数组大小应该是size+1
        arr: make([]int,size+1),
    }
}

// 判断队列是否满：(end+1)%size == start
func (this *queue) isFull() bool {
    return (this.end+1)%this.size == this.start
}

// 判断队列是否为空
func (this *queue) isEmpty() bool {
    return this.end == this.start
}

// 出队
func (this *queue) pop() (int,error) {
    if this.isEmpty() {
        return 0,errors.New("queue is empty")
    }
    data := this.arr[this.start]
    if this.start == this.size {
        this.start = 0
    } else {
        this.start++
    }
    return data,nil
}

// 入队
func (this *queue) put(data int) (bool,error) {
    if this.isFull() {
        return false,errors.New("queue is full")
    }
    // 元素入队
    this.arr[this.end]=data
    // end后移
    if this.end == this.size-1 {
        this.end=0
    } else {
        this.end++
    }
    return true,nil
}

// 判断当前队列中有几个元素
func (this *queue) num() int {
    if this.isEmpty() {
        return 0
    }
    if this.isFull() {
        return this.size-1
    }
    if this.start > this.end {
        return this.size-(this.start-this.end)
    } else {
        return this.end-this.start
    }
}

// 遍历队列
/*func (this *queue) list() {
    total := this.num()
    //fmt.Println("total =",total)
    index := this.start
    for total>0 {
        if index > this.size-1 {
            index=0
        }
        fmt.Printf("%d,",this.arr[index])
        index++
        total--
    }
    fmt.Println()
}*/

// 遍历队列：以数组形式返回
func (this *queue) list() []int {
    total := this.num()
    res:=make([]int,total)
    index := this.start
    i:=0
    for total>0 {
        if index > this.size-1 {
            index=0
        }
        res[i]=this.arr[index]
        index++
        total--
        i++
    }
    return res
}